package {
	import de.polygonal.ds.Array2;
	import de.polygonal.ds.Heap;
	
	import flash.display.BitmapData;
	import flash.display.Sprite;
	import flash.events.KeyboardEvent;
	import flash.events.MouseEvent;
	import flash.geom.Matrix;
	import flash.ui.Keyboard;
	import flash.utils.getTimer;
	
	import pathFinder.BaseTile;

	[SWF(width="800", height="600", frameRate="40", backgroundColor="#FFFFFF")]
	
	public class AstarTest extends Sprite
	{
		private var ctrlDown:Boolean=false;
		private var map:Array2;
		private var start:BaseTile;
		private var dest:BaseTile;
		private var pathSprite:Sprite;
		private var startPoint:Sprite;
		private var endPoint:Sprite;
		private var mapScale:int = 8;
		
		public function AstarTest()
		{
			stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
			stage.addEventListener(KeyboardEvent.KEY_UP, onKeyUP);
			stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
			
			pathSprite = new Sprite();
			addChild(pathSprite);
			
			addDragPoints();
		}
		
		private function createMap():void
		{
			var scale:Number = 1/mapScale;
			var scaledContent:BitmapData = new BitmapData(stage.stageWidth*scale, stage.stageHeight*scale, false, 0xFFFFFF);
			var scaleMatrix:Matrix = new Matrix();
			scaleMatrix.scale(scale, scale);
			scaledContent.draw(this, scaleMatrix);
			
			map = new Array2(scaledContent.width, scaledContent.height);
			
			var pixel:uint;
			var grey:uint;
			var cost:int;
			var i:int;
			var j:int;
			for (i=0; i<scaledContent.width; ++i){
				for (j=0; j<scaledContent.height; ++j){
					pixel = scaledContent.getPixel(i,j);
					cost = (pixel & 0xFF)+1;
					//trace("SET TILE I "+i+" J "+j+" cost "+cost+" walkable "+(cost != 255));
					map.set(i,j, cost < 255 ? new BaseTile(i,j,cost): null);
				}
			}
			
			var mapWidth:int = map._w;
			var mapHeight:int = map._h;
			
			var northEast:int;
			var southEast:int;
			var southWest:int;
			var northWest:int;
			var north:int;			
			var east:int;			
			var south:int;
			var west:int;
			var tile:BaseTile;

			for (i=0; i<mapWidth; ++i){
				for (j=0; j<mapHeight; ++j){
					
					tile = BaseTile(map.get(i,j));
					
					if(!tile)
						continue;
					
					north 		= map.get(i, j-1) == null ? 0 : 1;
					northEast	= map.get(i+1, j-1) == null ? 0 : 1;
					east 		= map.get(i+1, j) == null ? 0 : 1;
					southEast	= map.get(i+1, j+1) == null ? 0 : 1;
					south		= map.get(i, j+1) == null ? 0 : 1;
					southWest 	= map.get(i-1, j+1) == null ? 0 : 1;
					west	 	= map.get(i-1, j) == null ? 0 : 1;
					northWest 	= map.get(i-1, j-1) == null ? 0 : 1;

					tile.neighbours = north << 14 | northEast << 12 | east << 10 | southEast << 8 | south << 6 | southWest << 4 | west << 2 | northWest ;
					//trace("TILE AT "+i+":"+j+" "+tile.neighbours);
				}
			}		
		}
		
		
		private function aStar(startTile:BaseTile, destTile:BaseTile):Boolean
		{
			resetMap();
			var heap:Heap = new Heap(1024, true);
			heap.enqueue(startTile);
			
			var currentTile:BaseTile;
			var neighbours:Array;
			
			var north:int;
			var northEast:int;
			var east:int;
			var southEast:int;
			var south:int;
			var southWest:int;
			var west:int;
			var northWest:int;
			var i:int;
			var neighbourTile:BaseTile;
			var distance:int;
			
			while(!heap.isEmpty()){
				currentTile = BaseTile(heap.front());
				heap.dequeue();
				
				if(!currentTile.marked){
					currentTile.marked = true;
					
					if(currentTile == destTile){
						return true;
					}
					
					neighbours = [];
					
					north 		= currentTile.neighbours >> 14 & 1;
					northEast	= currentTile.neighbours >> 12 & 1;
					east		= currentTile.neighbours >> 10 & 1;
					southEast	= currentTile.neighbours >> 8 & 1;
					south		= currentTile.neighbours >> 6 & 1;
					southWest	= currentTile.neighbours >> 4 & 1;
					west		= currentTile.neighbours >> 2 & 1;
					northWest	= currentTile.neighbours & 1;
					
					if(north==1){
						neighbours.push( map.get(currentTile.x, currentTile.y-1));
					}
					if(northEast==1){
						neighbours.push( map.get(currentTile.x+1, currentTile.y-1));
					}
					if(east==1){
						neighbours.push( map.get(currentTile.x+1, currentTile.y));
					}
					if(southEast==1){
						neighbours.push( map.get(currentTile.x+1, currentTile.y+1));
					}
					if(south==1){
						neighbours.push( map.get(currentTile.x, currentTile.y+1));
					}
					if(southWest==1){
						neighbours.push( map.get(currentTile.x-1, currentTile.y+1));
					}
					if(west==1){
						neighbours.push( map.get(currentTile.x-1, currentTile.y));
					}
					if(northWest==1){
						neighbours.push( map.get(currentTile.x-1, currentTile.y-1));
					}
										
					for (i=0; i<neighbours.length; i++){
						neighbourTile =  BaseTile(neighbours[i]);
						if(!neighbourTile.marked){
							
							distance = calculateDistance(currentTile, neighbourTile) + currentTile.h;
							
							if(neighbourTile.parent){
								if(distance < neighbourTile.h){
									neighbourTile.parent = currentTile;
									neighbourTile.h = distance;
								}else{
									continue;
								}
							}else{
								neighbourTile.parent = 	currentTile;
								neighbourTile.h = distance;
							}
							heap.enqueue(neighbourTile);							
						}							
					}												
				}						
			}			

			return false;	
		}
		
		private function getPath(destTile:BaseTile):Array
		{
			var path:Array =  [];
			while(destTile){
				path.push(destTile);
				destTile = destTile.parent;
			}
			return path;			
		}
		
		private function simplify(path:Array, radius:Number):Array
		{
			var newPoints:Array = [];
			
			var q:BaseTile = path[0];
			
			newPoints.push(q);
			
			var maxdist:Number = radius * radius;
			var p:BaseTile;
			for (var i:uint = 1; i < path.length; ++i) {
				p = path[i];
				if ((p.x - q.x)*(p.x - q.x) + (p.y - q.y)*(p.y - q.y) > maxdist) {
					newPoints.push(p);
					q = p;
				}
			}
			
			if(newPoints[newPoints.length-1] != q)			
				newPoints.push(q);
			if(path[path.length-1] != q)			
				newPoints.push(path[path.length-1]);	
			
			return newPoints;
		}
		
		private function drawPath(path:Array, color:uint):void
		{			
			var tile:BaseTile;
			var tile2:BaseTile;
			
			pathSprite.graphics.lineStyle(2, color);
			var i2:int;
			for (var i:int=0; i<path.length-1;i++){
				i2 = (i+1)%path.length;				
				tile= path[i];
				tile2 = path[i2]
				pathSprite.graphics.moveTo(tile.x*mapScale,tile.y*mapScale);
				pathSprite.graphics.lineTo(tile2.x*mapScale,tile2.y*mapScale);	
			}				
		}
		
		private function calculateDistance(startTile:BaseTile, destTile:BaseTile):int
		{
			//TODO not optimized yet
			
			//Euclidian distance
			/*var dx:Number = startTile.x - destTile.x;
			var dy:Number = startTile.y - destTile.y;
			return  Math.sqrt((dx * dx) + (dy * dy));
			*/
			// Diagonal distance
			/*var dx:Number = Math.abs(startTile.x - destTile.x);
			var dy:Number = Math.abs(startTile.y - destTile.y);
			return Math.max(dx,dy);
			*/
			
			// Manhattan distance
			//Math.abs(startTile.x - destTile.x) + Math.abs(startTile.y - destTile.y)
			var dx:int = startTile.x - destTile.x;
			var dy:int = startTile.y - destTile.y;
			dx = (dx ^ (dx >> 31)) - (dx >> 31);
			dy = (dy ^ (dy >> 31)) - (dy >> 31);
			return dx + dy;			
		}
			
		
		private function resetMap():void
		{
		
			var mapWidth:int = map._w;
			var mapHeight:int = map._h;
			var tile:BaseTile;
			for (var i:int=0; i<mapWidth; ++i){
				for (var j:int=0; j<mapHeight; ++j){
					tile = BaseTile(map.get(i,j));
					if(tile){
						tile.marked = false;
						tile.parent = null;
					}		
				}
			}		
		}

		private function onMouseDown(e:MouseEvent):void
		{			
			stage.addEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
			stage.addEventListener(MouseEvent.MOUSE_UP, onMouseUP);
		}
		
		private function onMouseMove(e:MouseEvent):void
		{
			if(ctrlDown){
				graphics.beginFill(0xFFFFFF);
				graphics.drawCircle(e.stageX, e.stageY, 25);
				graphics.endFill();	
			}else{
				graphics.beginFill(0x000000);
				graphics.drawCircle(e.stageX, e.stageY, 25);
				graphics.endFill();
			}
		}
		
		private function onKeyDown(e:KeyboardEvent):void
		{
			if(e.keyCode==Keyboard.CONTROL){
				ctrlDown = true;
			}	
		}		
		
		private function onMouseUP(e:MouseEvent):void
		{
			stage.removeEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
			stage.removeEventListener(MouseEvent.MOUSE_UP, onMouseUP);
			createMap();
		}
		
		private function onKeyUP(e:KeyboardEvent):void
		{
			switch(e.keyCode){
				case Keyboard.F1:
					var then:int = getTimer();
					createMap();		
					var now:int = getTimer();
					trace("CREATING MAP TOOK "+(now-then));
				break;	
				case Keyboard.F2:
					aStar(BaseTile(map.get(0,0)), BaseTile(map.get(map._h-1, map._w-1)));	
				break;	
				case Keyboard.F3:
				break;
				case Keyboard.CONTROL:
					ctrlDown = false;
				break;			
			}
		}
		
		private function addDragPoints():void
		{
			startPoint = new Sprite();
			startPoint.graphics.beginFill(0xFF0000);
			startPoint.graphics.drawCircle(-5,-5, 10);
			startPoint.x = startPoint.y = 100;
			addChild(startPoint);
			endPoint = new Sprite();
			endPoint.graphics.beginFill(0x00FF00);
			endPoint.graphics.drawCircle(-5,-5, 10);
			endPoint.x = endPoint.y = 200;
			addChild(endPoint);	
			
			startPoint.addEventListener(MouseEvent.MOUSE_DOWN, onStartMouseDown);
			startPoint.addEventListener(MouseEvent.MOUSE_UP, onStartMouseUp);
			endPoint.addEventListener(MouseEvent.MOUSE_DOWN, onEndMouseDown);
			endPoint.addEventListener(MouseEvent.MOUSE_UP, onEndMouseUp);
			
		}
		
		private function onStartMouseDown(e:MouseEvent):void
		{
			e.stopImmediatePropagation();
			startPoint.startDrag();
		}
		
		private function onEndMouseDown(e:MouseEvent):void
		{	
			e.stopImmediatePropagation();
			endPoint.startDrag();
			endPoint.addEventListener(MouseEvent.MOUSE_MOVE, onEndMouseMove);
		}
		
		private function onEndMouseMove(e:MouseEvent):void
		{
			if(!map)
				return;
				
			dest = BaseTile(map.get(e.stageX/mapScale, e.stageY/mapScale));
			findPath();
		}
		
		private function findPath():void
		{
			if(start && dest){
				var then:uint = getTimer();
				trace("PATH FOUND "+aStar(start, dest));
				
				var path:Array = getPath(dest);
				pathSprite.graphics.clear();
				drawPath(path, 0xFFFF00);
				drawPath(simplify(path, 2), 0xFF0000);
				
				var now:uint = getTimer();
				
				trace("TOOK "+(now-then))
			}	
		}
		
		private function onStartMouseUp(e:MouseEvent):void
		{
			startPoint.stopDrag();	
			if(map){
				start = BaseTile(map.get(e.stageX/mapScale, e.stageY/mapScale));
			}
			
			findPath();
		}
		
		private function onEndMouseUp(e:MouseEvent):void
		{
			endPoint.stopDrag();	
			endPoint.removeEventListener(MouseEvent.MOUSE_MOVE, onEndMouseMove);
		}
	}
}
